While images have always been incorporated into documents as an efficient way to convey information to readers, the exploding use of personal computers coupled with computerization of an increasingly diverse array of image-related applications has substantially increased the need to manipulate images in digital form. These manipulations frequently include, inter alia, scaling, rotating and halftoning.
Beginning several years ago and continuing with increasing use to the present, documentary images are often processed through a computer using a so-called page description language. Such a language allows a user to define objects, such as an image, that are to appear on a printed page and allows the objects to be processed in a desired fashion and then accurately positioned with respect to each other in order to properly form an entire page. To provide maximum flexibility to a user in processing a digital image, a page description language would need to support, with floating point precision, both arbitrary uniform and anamorphic image scaling within finite bounds, image rotation by an arbitrary angle, and halftoning with arbitrary screen angles and screen rulings. In order to assure that a documentary image properly "mates up" with other objects on a page, these image processing functions must be very accurately implemented, otherwise artifacts or other errors will appear on the page, when printed.
While several different page description languages are currently in use, serious limitations exist in the two basic approaches through which these languages have been traditionally implemented to perform, inter alia, image scaling and rotation.
Specifically, one basic approach widely used in the art relies on storing an entire image within a random access frame memory and then operating on the individual bits of the image situated therein. This approach, hereinafter referred to as the "full frame memory" approach, may involve sequentially reading the image, bit-by-bit, using suitable incrementing memory addresses to generate appropriately rotated image data to yield a rotated image. As known in the art, scaling may involve, for example, adding or deleting data to or from selected pixel locations in the memory in order to change the scale of the image, as desired. This overall approach requires a sufficiently large frame memory that also provides relatively fast read-write random access. Unfortunately, for an 8-by-10 inch (approximately 20-by-25 cm) continuous tone image printed at a resolution of 300 dots/inch (approximately 118 dots/cm) which is readily obtainable with currently available output writers, e.g. laser printers, the frame memory would require approximately 7 MBytes. A memory of this size, particularly when fabricated from currently available high speed random access memory (RAM) circuits, tends to be very expensive. The inordinate cost of such a frame memory generally precludes its use in a low cost printer. Furthermore, even with such a large, fast memory, image scaling and rotation are often performed through a software based process executing in a microprocessor and, as such, for an entire image, tends to be relatively slow.
In view of the practical memory limitation, the art has, for some time, also taught that scaling and rotation could alternately be performed on a "tile-based" approach. Here, an image is first partitioned into small uniform regions called "tiles" each of which is then separately and appropriately processed. Typically, a tile is significantly smaller than the entire image. Once a tile is processed to yield an output tile, that output tile is then written into a spatially corresponding region in an output buffer, and so on for all such tiles until an entire image has been formed of output tiles.
Given these two approaches, tiling offers several distinct advantages. First, by drastically reducing the size of a tile down from that of the entire image, memory requirements for a high speed frame memory are substantially reduced from, for example, 7 MBytes for storing an entire image to perhaps 10 KBytes for storing a single tile currently being processed. This, in turn, obviates the need for a large full size high speed frame memory thereby simplifying and significantly reducing the cost of the system memory. While an image size output buffer would still be required, this buffer would not need to function as a high speed random access memory and thus can be fabricated from relatively slow and inexpensive memory circuits. Furthermore, by processing a single tile at a time, data transfers involving the frame memory are reduced to the data required just for a particular tile rather than that of the entire image as in the "full frame memory" approach. Consequently, the operations required to perform these memory transfers are greatly simplified and, as such, merely become an incidental portion of the overall tile-based processing. Moreover, by processing only a relatively small amount of data at any one time, specialized hardware circuits can be easily fabricated to rapidly process an entire tile and thereby accelerate the rate at which the entire image can be rotated and/or scaled over that associated with the "full frame memory" approach. Lastly, tile-based implementations tend to readily lend themselves to pipelined and parallel processing through which appropriate tile processing hardware is duplicated and operated on a parallel and time-staggered basis to permit several tiles to be collectively processed at once. This, in turn, further accelerates the overall process of image scaling and/or rotation. Advantageously, such implementations can easily be upwardly scaled in size, consistent with cost-performance tradeoffs, to achieve a desired throughput level.
Unfortunately, for all the advantages exhibited by tile-based scaling and rotation, a tile-based approach, particularly when used for halftoning, necessitates that each output tile must be very accurately placed in the output buffer else visible flaws will occur in the image. Specifically, for a halftoned image with a 50% tint factor, a one pixel offset in the halftoning pattern between adjacent tiles appears to cause visible artifacts to appear in the image. These artifacts take the form of "zig-zag" lines that occur along the tile boundaries all throughout the image. As a result, if an image is to be subsequently halftoned, then a screener operating on those tiles is required to obtain each tile from the output buffer, screen that tile and place that tile back into the output buffer with a one-bit accuracy. Achieving and maintaining such a high accuracy throughout the entire halftoning process for an image has proven to be extremely difficult to attain in practice.
At first blush, one might think that this accuracy could be relaxed and the "zig-zag" pattern eliminated by appropriately smoothing the boundaries of the halftoned tiles. Specifically, such smoothing, implemented through low pass spatial filtering, would reduce the visual impact of rounding errors and resulting tile mis-alignment that would otherwise result when floating point address values are truncated into real integer addresses which, in turn, are used to address an output buffer into which the halftoned tiles are re-assembled. While such filtering does appear to reduce visible tile mis-alignment, unfortunately this filtering breaks up and thereby corrupts the underlying halftone dot structure in the image. Therefore, tile boundary filtering does not seem to offer a viable solution and one-bit accuracies do need to be maintained in tile-based image processing.
Furthermore, apart from tiling, commercially available screeners are expensive, require inordinate amounts of memory and often do not possess the capability of performing image scaling and/or rotation.
In addition, image scaling and rotation are frequently carried out in currently available image processing apparatus as "front-end" operations, i.e. in circuitry situated near an image scanner in a chain of image processing circuits; while screening is carried out as a "back-end" operation, i.e. in circuitry associated with an output writer. Either operation generally has little, and oftentimes no knowledge, of the other with, as a result, artifacts and other adverse consequences frequently manifesting themselves in the image. Since page description languages perform post-processing, i.e. these languages process an image as they "find it" these languages provide no opportunity to optimize an image for operations that have previously been performed on it, such as "front-end" scaling or rotation. As such, the specific implementation of these languages, as currently used, does not eliminate adverse affects, such as Moire patterns and aliasing, that might result from interaction between various characteristics of these "front-end" operations, such as for example sampling frequencies and pixel placement, with similar corresponding characteristics associated with the halftoning process and the output writer.
Moreover, commercially available screeners also tend to be inordinately slow. Accordingly, if such a screener were to be used in implementing a page description language, then the resulting throughput provided thereby would be substantially less than the speed, in pages/minute (ppm), of currently available output writers, such as upwards of 70 ppm, and would thus pose a serious bottleneck. Inordinately slow speeds would tend to frustrate users, who, in turn, would rather shy away from and not incorporate images into documents than wait the needed time for each of these images to be processed and printed.
In spite of the basic drawbacks noted above, the advantages inherent in a tiled-based approach, particularly those flowing from the reduction in size and cost of the frame buffer, strongly support its use.
Therefore, a general need exists in the art for a tile-based technique that can very accurately and inexpensively implement image rotation, scaling and halftoning in a post-processing environment. Furthermore, a specific need exists to implement tile-based scaling, rotating and halftoning in a manner that can significantly accelerate the throughput of a page description language to approach that of currently available output writers. Advantageously, the incorporation of such a technique in an output writer will significantly hasten the use of documentary images.
Furthermore, output halftone images produced through use of a digital screener and printed on a digital output writers, such as laser printers with one or more marking lasers, have a tendency to contain unwanted and visually objectionable Moire patterns (and other similar artifacts). One cause of these patterns, i.e. so-called "screener induced" Moire, results from spatial interactions that arise between periodic two-dimensional sampling that occurs in the screening process itself with a two-dimensional pattern at which output spots are produced by the writer. In particular, digital screeners typically rely on periodically sampling a pre-defined pattern, such as halftone reference cell or a pre-defined threshold matrix, on a grid-like pattern (i.e. the "halftone sampling" grid) to produce a halftone dot pattern. Digital output writers rely on generating output spots also on a pre-defined grid-like pattern (i.e. the "writing" grid), but with each point on the grid being either light or dark and spatially corresponding to a position of a given dot in a two-dimensional writing area. The spacing between adjacent points on the writing grid, i.e. adjacent dots in the image, is determined by the output resolution of the writer. While, for any output writer, the writing grid is fixed in both resolution and orientation (with its axes being parallel to the vertical and horizontal directions of a printed page); the "halftone sampling" grid is intentionally varied both as to its resolution, as dictated by the screen ruling, and its angular orientation, as dictated by the screen angle, desired by a user. A halftone dot is typically formed of several successive horizontally oriented rasters of writing spots with the number of individual writing spots that are darkened, in any such raster, to form the dot being determined by the size of the underlying continuous tone value (and, where used, the associated halftone reference cell). Inasmuch as the halftone sampling and writing grids often have different elemental spacings (resolutions) as well as different angular orientations, sampled data generated by the halftone sampling grid interacts with the writing grid to produce beat patterns that manifest themselves, in the output image, as, e.g., Moire patterns. Moreover, in a digital halftone image, Moire patterns (and similar image artifacts) can result from several different sources: only one of which is screener induced Moire. In this regard, Moire patterns can also result from superimposing primary color (cyan, magenta, yellow and black--C,Y,M,K) halftone separations to yield a halftone color image. Specifically, Moire patterns could be generated by spatial interactions of the halftone dot patterns in the overlaid separations. If such spatial interactions are sufficiently strong, regardless of their actual source, then the resulting Moire patterns can be quite noticeable and visually objectionable. The presence of screener induced Moire not only adds to the source of image Moire, but also screener induced Moire also camouflages the source of image Moire, to a user, thereby greatly complicating and frustrating the removal of all image Moire from a halftone color image. At first blush, one would think that when Moire patterns occur in a screened halftone image, a user merely needs to change the screen ruling and/or screen angle to values that shift the beat frequencies to far less noticeable Moire patterns. Unfortunately, doing so, particularly where two (or more) sources of the Moire patterns simultaneously exist, can be an extremely tedious, time-consuming and labor-intensive process.
Therefore, a specific need exists in the art for a technique that can be employed in a tile-based image processing apparatus, which performs halftoning, for substantially suppressing (masking) screener induced artifacts, such as Moire patterns. By substantially eliminating one cause of these artifacts from digitally halftoned images that are to be produced on a digital output writer, the quality of the resulting images is likely to advantageously increase, thereby further hastening and expanding the use of documentary images.